<!DOCTYPE html>
<html lang="en"><head><script src="/livereload.js?mindelay=10&amp;v=2&amp;port=1313&amp;path=livereload" data-no-instant defer></script>
  <meta charset="utf-8" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <meta name="robots" content="noindex, nofollow" />
  <link rel="icon shortcut" href="/favicon.ico" sizes="32x32" />
<link rel="icon" href="/favicon.svg" type="image/svg+xml" />
<link rel="icon" href="/favicon-dark.svg" type="image/svg+xml" media="(prefers-color-scheme: dark)" />
<link rel="icon" href="/favicon-16x16.png" type="image/png" sizes="16x16" />
<link rel="icon" href="/favicon-32x32.png" type="image/png" sizes="32x32" />
<link rel="apple-touch-icon" href="/apple-touch-icon.png" sizes="180x180" />
<link fetchpriority="low" href="/site.webmanifest" rel="manifest" />

  <title>第 23 章：排序与归并 – PostgreSQL 14 Internals</title>
  <meta name="description" content="23.1 归并连接 归并连接处理按连接键排序的数据集，并返回以类似方式排序后的结果。输入数据集可能在索引扫描后预排序；否则，执行器必须在真正开始归并之前对它们进行排序。1
23.1.1 归并排序数据集 让我们看一个归并连接的例子；在执行计划中由 Merge Join 节点表示：2
=&gt; EXPLAIN (costs off) SELECT * FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no ORDER BY t.ticket_no; QUERY PLAN −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− Merge Join Merge Cond: (t.ticket_no = tf.ticket_no) −&gt; Index Scan using tickets_pkey on tickets t −&gt; Index Scan using ticket_flights_pkey on ticket_flights tf (4 rows) 优化器更喜欢这种连接方式，因为它按照 ORDER BY 子句定义的方式返回排序后的结果。在选择计划时，优化器会注意到数据集的排序顺序，并且除非确实需要，否则不会执行任何排序。例如，如果归并连接生成的数据集已经具有合适的排序顺序，那么它可以直接在之后的归并连接中使用：" />

  
    <link rel="canonical" href="//localhost:1313/docs/chapter23/" itemprop="url" />
  

  

<meta property="og:title" content="第 23 章：排序与归并" />
<meta property="og:description" content="" />
<meta property="og:type" content="website" />
<meta property="og:url" content="//localhost:1313/docs/chapter23/" />

  
  <meta itemprop="name" content="第 23 章：排序与归并">
  <meta itemprop="description" content="23.1 归并连接 归并连接处理按连接键排序的数据集，并返回以类似方式排序后的结果。输入数据集可能在索引扫描后预排序；否则，执行器必须在真正开始归并之前对它们进行排序。1
23.1.1 归并排序数据集 让我们看一个归并连接的例子；在执行计划中由 Merge Join 节点表示：2
=&gt; EXPLAIN (costs off) SELECT * FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no ORDER BY t.ticket_no; QUERY PLAN −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− Merge Join Merge Cond: (t.ticket_no = tf.ticket_no) −&gt; Index Scan using tickets_pkey on tickets t −&gt; Index Scan using ticket_flights_pkey on ticket_flights tf (4 rows) 优化器更喜欢这种连接方式，因为它按照 ORDER BY 子句定义的方式返回排序后的结果。在选择计划时，优化器会注意到数据集的排序顺序，并且除非确实需要，否则不会执行任何排序。例如，如果归并连接生成的数据集已经具有合适的排序顺序，那么它可以直接在之后的归并连接中使用：">
  <meta itemprop="wordCount" content="1828">
  <meta name="twitter:card" content="summary">
  <meta name="twitter:title" content="第 23 章：排序与归并">
  <meta name="twitter:description" content="23.1 归并连接 归并连接处理按连接键排序的数据集，并返回以类似方式排序后的结果。输入数据集可能在索引扫描后预排序；否则，执行器必须在真正开始归并之前对它们进行排序。1
23.1.1 归并排序数据集 让我们看一个归并连接的例子；在执行计划中由 Merge Join 节点表示：2
=&gt; EXPLAIN (costs off) SELECT * FROM tickets t JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no ORDER BY t.ticket_no; QUERY PLAN −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− Merge Join Merge Cond: (t.ticket_no = tf.ticket_no) −&gt; Index Scan using tickets_pkey on tickets t −&gt; Index Scan using ticket_flights_pkey on ticket_flights tf (4 rows) 优化器更喜欢这种连接方式，因为它按照 ORDER BY 子句定义的方式返回排序后的结果。在选择计划时，优化器会注意到数据集的排序顺序，并且除非确实需要，否则不会执行任何排序。例如，如果归并连接生成的数据集已经具有合适的排序顺序，那么它可以直接在之后的归并连接中使用：">

    <link href="/css/compiled/main.css" rel="stylesheet" />



  <link href="/css/custom.css" rel="stylesheet" />





  <script>
     
    const defaultTheme = 'light';

    const setDarkTheme = () => {
      document.documentElement.classList.add("dark");
      document.documentElement.style.colorScheme = "dark";
    }
    const setLightTheme = () => {
      document.documentElement.classList.remove("dark");
      document.documentElement.style.colorScheme = "light";
    }

    if ("color-theme" in localStorage) {
      localStorage.getItem("color-theme") === "dark" ? setDarkTheme() : setLightTheme();
    } else {
      defaultTheme === "dark" ? setDarkTheme() : setLightTheme();
      if (defaultTheme === "system") {
        window.matchMedia("(prefers-color-scheme: dark)").matches ? setDarkTheme() : setLightTheme();
      }
    }
  </script>

  
</head>
<body dir="ltr"><div class="nav-container hx-sticky hx-top-0 hx-z-20 hx-w-full hx-bg-transparent print:hx-hidden">
  <div class="nav-container-blur hx-pointer-events-none hx-absolute hx-z-[-1] hx-h-full hx-w-full hx-bg-white dark:hx-bg-dark hx-shadow-[0_2px_4px_rgba(0,0,0,.02),0_1px_0_rgba(0,0,0,.06)] contrast-more:hx-shadow-[0_0_0_1px_#000] dark:hx-shadow-[0_-1px_0_rgba(255,255,255,.1)_inset] contrast-more:dark:hx-shadow-[0_0_0_1px_#fff]"></div>

  <nav class="hx-mx-auto hx-flex hx-items-center hx-justify-end hx-gap-2 hx-h-16 hx-px-6 hx-max-w-[90rem]">
    <a class="hx-flex hx-items-center hover:hx-opacity-75 ltr:hx-mr-auto rtl:hx-ml-auto" href="/">
        <img class="hx-block dark:hx-hidden" src="/images/postgresql-elephant-in-potential.svg" alt="PostgreSQL 14 Internals" height="30" width="45" />
        <img class="hx-hidden dark:hx-block" src="/images/postgresql-elephant-in-power.svg" alt="PostgreSQL 14 Internals" height="30" width="45" />
        <span class="hx-mx-2 hx-font-extrabold hx-inline hx-select-none" title="PostgreSQL 14 Internals">PostgreSQL 14 Internals</span>
    </a><a
            title="Docs"
            href="/docs"
            
            class="hx-text-sm contrast-more:hx-text-gray-700 contrast-more:dark:hx-text-gray-100 hx-relative -hx-ml-2 hx-hidden hx-whitespace-nowrap hx-p-2 md:hx-inline-block hx-font-medium"
          >
            <span class="hx-text-center">Docs</span>
          </a><a
            title="About"
            href="/about"
            
            class="hx-text-sm contrast-more:hx-text-gray-700 contrast-more:dark:hx-text-gray-100 hx-relative -hx-ml-2 hx-hidden hx-whitespace-nowrap hx-p-2 md:hx-inline-block hx-text-gray-600 hover:hx-text-gray-800 dark:hx-text-gray-400 dark:hover:hx-text-gray-200"
          >
            <span class="hx-text-center">About</span>
          </a><a
            title="Contact ↗"
            href="https://github.com/xiongcccc"
            target="_blank" rel="noreferer"
            class="hx-text-sm contrast-more:hx-text-gray-700 contrast-more:dark:hx-text-gray-100 hx-relative -hx-ml-2 hx-hidden hx-whitespace-nowrap hx-p-2 md:hx-inline-block hx-text-gray-600 hover:hx-text-gray-800 dark:hx-text-gray-400 dark:hover:hx-text-gray-200"
          >
            <span class="hx-text-center">Contact ↗</span>
          </a><div class="search-wrapper hx-relative md:hx-w-64">
  <div class="hx-relative hx-flex hx-items-center hx-text-gray-900 contrast-more:hx-text-gray-800 dark:hx-text-gray-300 contrast-more:dark:hx-text-gray-300">
    <input
      placeholder="Search..."
      class="search-input hx-block hx-w-full hx-appearance-none hx-rounded-lg hx-px-3 hx-py-2 hx-transition-colors hx-text-base hx-leading-tight md:hx-text-sm hx-bg-black/[.05] dark:hx-bg-gray-50/10 focus:hx-bg-white dark:focus:hx-bg-dark placeholder:hx-text-gray-500 dark:placeholder:hx-text-gray-400 contrast-more:hx-border contrast-more:hx-border-current"
      type="search"
      value=""
      spellcheck="false"
    />
    <kbd
      class="hx-absolute hx-my-1.5 hx-select-none ltr:hx-right-1.5 rtl:hx-left-1.5 hx-h-5 hx-rounded hx-bg-white hx-px-1.5 hx-font-mono hx-text-[10px] hx-font-medium hx-text-gray-500 hx-border dark:hx-border-gray-100/20 dark:hx-bg-dark/50 contrast-more:hx-border-current contrast-more:hx-text-current contrast-more:dark:hx-border-current hx-items-center hx-gap-1 hx-transition-opacity hx-pointer-events-none hx-hidden sm:hx-flex"
    >
      CTRL K
    </kbd>
  </div>

  <div>
    <ul
      class="search-results hextra-scrollbar hx-hidden hx-border hx-border-gray-200 hx-bg-white hx-text-gray-100 dark:hx-border-neutral-800 dark:hx-bg-neutral-900 hx-absolute hx-top-full hx-z-20 hx-mt-2 hx-overflow-auto hx-overscroll-contain hx-rounded-xl hx-py-2.5 hx-shadow-xl hx-max-h-[min(calc(50vh-11rem-env(safe-area-inset-bottom)),400px)] md:hx-max-h-[min(calc(100vh-5rem-env(safe-area-inset-bottom)),400px)] hx-inset-x-0 ltr:md:hx-left-auto rtl:md:hx-right-auto contrast-more:hx-border contrast-more:hx-border-gray-900 contrast-more:dark:hx-border-gray-50 hx-w-screen hx-min-h-[100px] hx-max-w-[min(calc(100vw-2rem),calc(100%+20rem))]"
      style="transition: max-height 0.2s ease 0s;"
    ></ul>
  </div>
</div>

          <a class="hx-p-2 hx-text-current" target="_blank" rel="noreferer" href="https://github.com/xiongcccc/xiongcccc.github.io" title="GitHub"><svg height=24 fill="currentColor" viewBox="3 3 18 18">
  <path d="M12 3C7.0275 3 3 7.12937 3 12.2276C3 16.3109 5.57625 19.7597 9.15374 20.9824C9.60374 21.0631 9.77249 20.7863 9.77249 20.5441C9.77249 20.3249 9.76125 19.5982 9.76125 18.8254C7.5 19.2522 6.915 18.2602 6.735 17.7412C6.63375 17.4759 6.19499 16.6569 5.8125 16.4378C5.4975 16.2647 5.0475 15.838 5.80124 15.8264C6.51 15.8149 7.01625 16.4954 7.18499 16.7723C7.99499 18.1679 9.28875 17.7758 9.80625 17.5335C9.885 16.9337 10.1212 16.53 10.38 16.2993C8.3775 16.0687 6.285 15.2728 6.285 11.7432C6.285 10.7397 6.63375 9.9092 7.20749 9.26326C7.1175 9.03257 6.8025 8.08674 7.2975 6.81794C7.2975 6.81794 8.05125 6.57571 9.77249 7.76377C10.4925 7.55615 11.2575 7.45234 12.0225 7.45234C12.7875 7.45234 13.5525 7.55615 14.2725 7.76377C15.9937 6.56418 16.7475 6.81794 16.7475 6.81794C17.2424 8.08674 16.9275 9.03257 16.8375 9.26326C17.4113 9.9092 17.76 10.7281 17.76 11.7432C17.76 15.2843 15.6563 16.0687 13.6537 16.2993C13.98 16.5877 14.2613 17.1414 14.2613 18.0065C14.2613 19.2407 14.25 20.2326 14.25 20.5441C14.25 20.7863 14.4188 21.0746 14.8688 20.9824C16.6554 20.364 18.2079 19.1866 19.3078 17.6162C20.4077 16.0457 20.9995 14.1611 21 12.2276C21 7.12937 16.9725 3 12 3Z"></path>
</svg>
<span class="hx-sr-only">GitHub</span>
          </a>
          <a class="hx-p-2 hx-text-current" target="_blank" rel="noreferer" href="https://twitter.com/" title="Twitter"><svg height=24 xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><path fill="currentColor" d="M389.2 48h70.6L305.6 224.2 487 464H345L233.7 318.6 106.5 464H35.8L200.7 275.5 26.8 48H172.4L272.9 180.9 389.2 48zM364.4 421.8h39.1L151.1 88h-42L364.4 421.8z"/></svg><span class="hx-sr-only">Twitter</span>
          </a><button type="button" aria-label="Menu" class="hamburger-menu -hx-mr-2 hx-rounded hx-p-2 active:hx-bg-gray-400/20 md:hx-hidden"><svg height=24 fill="none" viewBox="0 0 24 24" stroke="currentColor"><g><path stroke-linecap="round" stroke-linejoin="round" stroke-width="2" d="M4 8H20"></path></g><g><path stroke-linecap="round" stroke-linejoin="round" stroke-width="2" d="M4 16H20"></path></g></svg></button>
  </nav>
</div>

  <div class='hx-mx-auto hx-flex hx-max-w-[90rem]'>
    <div class="mobile-menu-overlay [transition:background-color_1.5s_ease] hx-fixed hx-inset-0 hx-z-10 hx-bg-black/80 dark:hx-bg-black/60 hx-hidden"></div>
<aside class="sidebar-container hx-flex hx-flex-col print:hx-hidden md:hx-top-16 md:hx-shrink-0 md:hx-w-64 md:hx-self-start max-md:[transform:translate3d(0,-100%,0)] md:hx-sticky">
  
  <div class="hx-px-4 hx-pt-4 md:hx-hidden">
    <div class="search-wrapper hx-relative md:hx-w-64">
  <div class="hx-relative hx-flex hx-items-center hx-text-gray-900 contrast-more:hx-text-gray-800 dark:hx-text-gray-300 contrast-more:dark:hx-text-gray-300">
    <input
      placeholder="Search..."
      class="search-input hx-block hx-w-full hx-appearance-none hx-rounded-lg hx-px-3 hx-py-2 hx-transition-colors hx-text-base hx-leading-tight md:hx-text-sm hx-bg-black/[.05] dark:hx-bg-gray-50/10 focus:hx-bg-white dark:focus:hx-bg-dark placeholder:hx-text-gray-500 dark:placeholder:hx-text-gray-400 contrast-more:hx-border contrast-more:hx-border-current"
      type="search"
      value=""
      spellcheck="false"
    />
    <kbd
      class="hx-absolute hx-my-1.5 hx-select-none ltr:hx-right-1.5 rtl:hx-left-1.5 hx-h-5 hx-rounded hx-bg-white hx-px-1.5 hx-font-mono hx-text-[10px] hx-font-medium hx-text-gray-500 hx-border dark:hx-border-gray-100/20 dark:hx-bg-dark/50 contrast-more:hx-border-current contrast-more:hx-text-current contrast-more:dark:hx-border-current hx-items-center hx-gap-1 hx-transition-opacity hx-pointer-events-none hx-hidden sm:hx-flex"
    >
      CTRL K
    </kbd>
  </div>

  <div>
    <ul
      class="search-results hextra-scrollbar hx-hidden hx-border hx-border-gray-200 hx-bg-white hx-text-gray-100 dark:hx-border-neutral-800 dark:hx-bg-neutral-900 hx-absolute hx-top-full hx-z-20 hx-mt-2 hx-overflow-auto hx-overscroll-contain hx-rounded-xl hx-py-2.5 hx-shadow-xl hx-max-h-[min(calc(50vh-11rem-env(safe-area-inset-bottom)),400px)] md:hx-max-h-[min(calc(100vh-5rem-env(safe-area-inset-bottom)),400px)] hx-inset-x-0 ltr:md:hx-left-auto rtl:md:hx-right-auto contrast-more:hx-border contrast-more:hx-border-gray-900 contrast-more:dark:hx-border-gray-50 hx-w-screen hx-min-h-[100px] hx-max-w-[min(calc(100vw-2rem),calc(100%+20rem))]"
      style="transition: max-height 0.2s ease 0s;"
    ></ul>
  </div>
</div>

  </div>
  <div class="hextra-scrollbar hx-overflow-y-auto hx-overflow-x-hidden hx-p-4 hx-grow md:hx-h-[calc(100vh-var(--navbar-height)-var(--menu-height))]">
    <ul class="hx-flex hx-flex-col hx-gap-1 md:hx-hidden">
      
      
          <li class=""><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/about/"
    
  >About
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/"
    
  >Docs
        <span class="hextra-sidebar-collapsible-button"><svg fill="none" viewBox="0 0 24 24" stroke="currentColor" class="hx-h-[18px] hx-min-w-[18px] hx-rounded-sm hx-p-0.5 hover:hx-bg-gray-800/5 dark:hover:hx-bg-gray-100/5"><path stroke-linecap="round" stroke-linejoin="round" stroke-width="2" d="M9 5l7 7-7 7" class="hx-origin-center hx-transition-transform rtl:-hx-rotate-180"></path></svg></span>
    </a><div class="ltr:hx-pr-0 hx-overflow-hidden">
        <ul class='hx-relative hx-flex hx-flex-col hx-gap-1 before:hx-absolute before:hx-inset-y-1 before:hx-w-px before:hx-bg-gray-200 before:hx-content-[""] ltr:hx-ml-3 ltr:hx-pl-3 ltr:before:hx-left-0 rtl:hx-mr-3 rtl:hx-pr-3 rtl:before:hx-right-0 dark:before:hx-bg-neutral-800'><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter01/"
    
  >第 1 章：介绍
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter02/"
    
  >第 2 章：隔离性
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter03/"
    
  >第 3 章：页与元组
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter04/"
    
  >第 4 章：快照
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter05/"
    
  >第 5 章：页剪枝与 HOT 更新
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter06/"
    
  >第 6 章：Vacuum 与 Autovacuum
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter07/"
    
  >第 7 章：冻结
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter08/"
    
  >第 8 章：重建表与索引
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter09/"
    
  >第 9 章：缓冲区缓存
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter10/"
    
  >第 10 章：预写式日志
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter11/"
    
  >第 11 章：WAL 模式
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter12/"
    
  >第 12 章：关系级锁
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter13/"
    
  >第 13 章：行级锁
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter14/"
    
  >第 14 章：多样的锁
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter15/"
    
  >第 15 章：内存结构上的锁
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter16/"
    
  >第 16 章：查询执行阶段
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter17/"
    
  >第 17 章：统计信息
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter18/"
    
  >第 18 章：表访问方法
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter19/"
    
  >第 19 章：索引访问方法
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter20/"
    
  >第 20 章：索引扫描
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter21/"
    
  >第 21 章：嵌套循环
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter22/"
    
  >第 22 章：哈希
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      sidebar-active-item hx-bg-primary-100 hx-font-semibold hx-text-primary-800 contrast-more:hx-border contrast-more:hx-border-primary-500 dark:hx-bg-primary-400/10 dark:hx-text-primary-600 contrast-more:dark:hx-border-primary-500"
    href="/docs/chapter23/"
    
  >第 23 章：排序与归并
    </a>
  
    <ul class='hx-flex hx-flex-col hx-gap-1 hx-relative before:hx-absolute before:hx-inset-y-1 before:hx-w-px before:hx-bg-gray-200 before:hx-content-[""] dark:before:hx-bg-neutral-800 ltr:hx-pl-3 ltr:before:hx-left-0 rtl:hx-pr-3 rtl:before:hx-right-0 ltr:hx-ml-3 rtl:hx-mr-3'><li>
              <a
                href="#231-%e5%bd%92%e5%b9%b6%e8%bf%9e%e6%8e%a5"
                class="hx-flex hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [word-break:break-word] hx-cursor-pointer [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] contrast-more:hx-border hx-gap-2 before:hx-opacity-25 before:hx-content-['#'] hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:hx-text-gray-900 contrast-more:dark:hx-text-gray-50 contrast-more:hx-border-transparent contrast-more:hover:hx-border-gray-900 contrast-more:dark:hover:hx-border-gray-50"
              >23.1 归并连接</a>
            </li>
          <li>
              <a
                href="#232-%e6%8e%92%e5%ba%8f"
                class="hx-flex hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [word-break:break-word] hx-cursor-pointer [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] contrast-more:hx-border hx-gap-2 before:hx-opacity-25 before:hx-content-['#'] hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:hx-text-gray-900 contrast-more:dark:hx-text-gray-50 contrast-more:hx-border-transparent contrast-more:hover:hx-border-gray-900 contrast-more:dark:hover:hx-border-gray-50"
              >23.2 排序</a>
            </li>
          <li>
              <a
                href="#233-%e9%9d%9e%e9%87%8d%e5%a4%8d%e5%80%bc%e5%92%8c%e5%88%86%e7%bb%84"
                class="hx-flex hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [word-break:break-word] hx-cursor-pointer [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] contrast-more:hx-border hx-gap-2 before:hx-opacity-25 before:hx-content-['#'] hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:hx-text-gray-900 contrast-more:dark:hx-text-gray-50 contrast-more:hx-border-transparent contrast-more:hover:hx-border-gray-900 contrast-more:dark:hover:hx-border-gray-50"
              >23.3 非重复值和分组</a>
            </li>
          <li>
              <a
                href="#234-%e8%bf%9e%e6%8e%a5%e6%96%b9%e5%bc%8f%e7%9a%84%e6%af%94%e8%be%83"
                class="hx-flex hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [word-break:break-word] hx-cursor-pointer [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] contrast-more:hx-border hx-gap-2 before:hx-opacity-25 before:hx-content-['#'] hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:hx-text-gray-900 contrast-more:dark:hx-text-gray-50 contrast-more:hx-border-transparent contrast-more:hover:hx-border-gray-900 contrast-more:dark:hover:hx-border-gray-50"
              >23.4 连接方式的比较</a>
            </li>
          </ul>
  
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter24/"
    
  >第 24 章：Hash
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter25/"
    
  >第 25 章：B-tree
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter26/"
    
  >第 26 章：GiST
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter27/"
    
  >第 27 章：SP-GiST
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter28/"
    
  >第 28 章：GIN
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter29/"
    
  >第 29 章：BRIN
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter30/"
    
  >结论
    </a>
              
            </li></ul>
      </div></li>
          <li class=""><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/recommend/"
    
  >Recommend
    </a></li>
    </ul>

    <ul class="hx-flex hx-flex-col hx-gap-1 max-md:hx-hidden">
        
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter01/"
    
  >第 1 章：介绍
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter02/"
    
  >第 2 章：隔离性
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter03/"
    
  >第 3 章：页与元组
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter04/"
    
  >第 4 章：快照
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter05/"
    
  >第 5 章：页剪枝与 HOT 更新
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter06/"
    
  >第 6 章：Vacuum 与 Autovacuum
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter07/"
    
  >第 7 章：冻结
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter08/"
    
  >第 8 章：重建表与索引
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter09/"
    
  >第 9 章：缓冲区缓存
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter10/"
    
  >第 10 章：预写式日志
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter11/"
    
  >第 11 章：WAL 模式
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter12/"
    
  >第 12 章：关系级锁
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter13/"
    
  >第 13 章：行级锁
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter14/"
    
  >第 14 章：多样的锁
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter15/"
    
  >第 15 章：内存结构上的锁
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter16/"
    
  >第 16 章：查询执行阶段
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter17/"
    
  >第 17 章：统计信息
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter18/"
    
  >第 18 章：表访问方法
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter19/"
    
  >第 19 章：索引访问方法
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter20/"
    
  >第 20 章：索引扫描
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter21/"
    
  >第 21 章：嵌套循环
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter22/"
    
  >第 22 章：哈希
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      sidebar-active-item hx-bg-primary-100 hx-font-semibold hx-text-primary-800 contrast-more:hx-border contrast-more:hx-border-primary-500 dark:hx-bg-primary-400/10 dark:hx-text-primary-600 contrast-more:dark:hx-border-primary-500"
    href="/docs/chapter23/"
    
  >第 23 章：排序与归并
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter24/"
    
  >第 24 章：Hash
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter25/"
    
  >第 25 章：B-tree
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter26/"
    
  >第 26 章：GiST
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter27/"
    
  >第 27 章：SP-GiST
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter28/"
    
  >第 28 章：GIN
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter29/"
    
  >第 29 章：BRIN
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter30/"
    
  >结论
    </a></li>
        
      </ul>
    </div>
  
  
    <div class="  hx-sticky hx-bottom-0 hx-bg-white dark:hx-bg-dark hx-mx-4 hx-py-4 hx-shadow-[0_-12px_16px_#fff] hx-flex hx-items-center hx-gap-2 dark:hx-border-neutral-800 dark:hx-shadow-[0_-12px_16px_#111] contrast-more:hx-border-neutral-400 contrast-more:hx-shadow-none contrast-more:dark:hx-shadow-none hx-border-t" data-toggle-animation="show"><div class="hx-flex hx-grow hx-flex-col"><button
  title="Change theme"
  data-theme="light"
  class="theme-toggle hx-group hx-h-7 hx-rounded-md hx-px-2 hx-text-left hx-text-xs hx-font-medium hx-text-gray-600 hx-transition-colors dark:hx-text-gray-400 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50"
  type="button"
  aria-label="Change theme"
>
  <div class="hx-flex hx-items-center hx-gap-2 hx-capitalize"><svg height=12 class="group-data-[theme=light]:hx-hidden" xmlns="http://www.w3.org/2000/svg" fill="none" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" aria-hidden="true"><path stroke-linecap="round" stroke-linejoin="round" d="M12 3v1m0 16v1m9-9h-1M4 12H3m15.364 6.364l-.707-.707M6.343 6.343l-.707-.707m12.728 0l-.707.707M6.343 17.657l-.707.707M16 12a4 4 0 11-8 0 4 4 0 018 0z"/></svg><span class="group-data-[theme=light]:hx-hidden">Light</span><svg height=12 class="group-data-[theme=dark]:hx-hidden" xmlns="http://www.w3.org/2000/svg" fill="none" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" aria-hidden="true"><path stroke-linecap="round" stroke-linejoin="round" d="M20.354 15.354A9 9 0 018.646 3.646 9.003 9.003 0 0012 21a9.003 9.003 0 008.354-5.646z"/></svg><span class="group-data-[theme=dark]:hx-hidden">Dark</span></div>
</button>
</div></div></aside>
    
<nav class="hextra-toc hx-order-last hx-hidden hx-w-64 hx-shrink-0 xl:hx-block print:hx-hidden hx-px-4" aria-label="table of contents">
    <div class="hextra-scrollbar hx-sticky hx-top-16 hx-overflow-y-auto hx-pr-4 hx-pt-6 hx-text-sm [hyphens:auto] hx-max-h-[calc(100vh-var(--navbar-height)-env(safe-area-inset-bottom))] ltr:hx--mr-4 rtl:hx--ml-4"><p class="hx-mb-4 hx-font-semibold hx-tracking-tight">On this page</p><ul>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="hx-font-semibold hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#231-%e5%bd%92%e5%b9%b6%e8%bf%9e%e6%8e%a5">23.1 归并连接
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2311-%e5%bd%92%e5%b9%b6%e6%8e%92%e5%ba%8f%e6%95%b0%e6%8d%ae%e9%9b%86">23.1.1 归并排序数据集
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2312-span-classmarginalia-data-notev-96%e5%b9%b6%e8%a1%8c%e6%a8%a1%e5%bc%8fspan">23.1.2 并行模式
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2313-%e8%b0%83%e6%95%b4">23.1.3 调整
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="hx-font-semibold hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#232-%e6%8e%92%e5%ba%8f">23.2 排序
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2321-%e5%bf%ab%e6%8e%92">23.2.1 快排
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2322-top-n-%e5%a0%86%e6%8e%92%e5%ba%8f">23.2.2 Top-N 堆排序
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2323-%e5%a4%96%e6%8e%92">23.2.3 外排
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2324-span-classmarginalia-data-notev-13%e5%a2%9e%e9%87%8f%e6%8e%92%e5%ba%8fspan">23.2.4 增量排序
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2325-span-classmarginalia-data-notev-10%e5%b9%b6%e8%a1%8c%e6%a8%a1%e5%bc%8fspan">23.2.5 并行模式
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="hx-font-semibold hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#233-%e9%9d%9e%e9%87%8d%e5%a4%8d%e5%80%bc%e5%92%8c%e5%88%86%e7%bb%84">23.3 非重复值和分组
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="hx-font-semibold hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#234-%e8%bf%9e%e6%8e%a5%e6%96%b9%e5%bc%8f%e7%9a%84%e6%af%94%e8%be%83">23.4 连接方式的比较
        </a>
      </li></ul>
      <div class="hx-mt-8 hx-border-t hx-bg-white hx-pt-8 hx-shadow-[0_-12px_16px_white] dark:hx-bg-dark dark:hx-shadow-[0_-12px_16px_#111] hx-sticky hx-bottom-0 hx-flex hx-flex-col hx-items-start hx-gap-2 hx-pb-8 dark:hx-border-neutral-800 contrast-more:hx-border-t contrast-more:hx-border-neutral-400 contrast-more:hx-shadow-none contrast-more:dark:hx-border-neutral-400">
        <button aria-hidden="true" id="backToTop" onClick="scrollUp();" class="hx-transition-all hx-duration-75 hx-opacity-0 hx-text-xs hx-font-medium hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-100 contrast-more:hx-text-gray-800 contrast-more:dark:hx-text-gray-50">
          <span>Scroll to top</span>
          <svg xmlns="http://www.w3.org/2000/svg" fill="none" viewBox="0 0 24 24" stroke-width="1.5" stroke="currentColor" class="hx-inline ltr:hx-ml-1 rtl:hx-mr-1 hx-h-3.5 hx-w-3.5 hx-border hx-rounded-full hx-border-gray-500 hover:hx-border-gray-900 dark:hx-border-gray-400 dark:hover:hx-border-gray-100 contrast-more:hx-border-gray-800 contrast-more:dark:hx-border-gray-50">
            <path stroke-linecap="round" stroke-linejoin="round" d="M4.5 15.75l7.5-7.5 7.5 7.5" />
          </svg>
        </button>
      </div>
    </div>
  </nav>


    <article class="hx-w-full hx-break-words hx-flex hx-min-h-[calc(100vh-var(--navbar-height))] hx-min-w-0 hx-justify-center hx-pb-8 hx-pr-[calc(env(safe-area-inset-right)-1.5rem)]">
      <main class="hx-w-full hx-min-w-0 hx-max-w-6xl hx-px-6 hx-pt-4 md:hx-px-12">
        
  <div class="hx-mt-1.5 hx-flex hx-items-center hx-gap-1 hx-overflow-hidden hx-text-sm hx-text-gray-500 dark:hx-text-gray-400 contrast-more:hx-text-current">
        <div class="hx-whitespace-nowrap hx-transition-colors hx-min-w-[24px] hx-overflow-hidden hx-text-ellipsis hover:hx-text-gray-900 dark:hover:hx-text-gray-100">
          <a href="/docs/">Docs</a>
        </div><svg class="hx-w-3.5 hx-shrink-0 rtl:-hx-rotate-180" xmlns="http://www.w3.org/2000/svg" fill="none" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" aria-hidden="true"><path stroke-linecap="round" stroke-linejoin="round" d="M9 5l7 7-7 7"/></svg><div class="hx-whitespace-nowrap hx-transition-colors hx-font-medium hx-text-gray-700 contrast-more:hx-font-bold contrast-more:hx-text-current dark:hx-text-gray-100 contrast-more:dark:hx-text-current">第 23 章：排序与归并</div>
  </div>

        <div class="content">
          <h1>第 23 章：排序与归并</h1>
          <h2>23.1 归并连接<span class="hx-absolute -hx-mt-20" id="231-归并连接"></span>
    <a href="#231-%e5%bd%92%e5%b9%b6%e8%bf%9e%e6%8e%a5" class="subheading-anchor" aria-label="Permalink for this section"></a></h2><p>归并连接处理按连接键排序的数据集，并返回以类似方式排序后的结果。输入数据集可能在索引扫描后预排序；否则，执行器必须在真正开始归并之前对它们进行排序。<sup id="fnref:1"><a href="#fn:1" class="footnote-ref" role="doc-noteref">1</a></sup></p>
<h3>23.1.1 归并排序数据集<span class="hx-absolute -hx-mt-20" id="2311-归并排序数据集"></span>
    <a href="#2311-%e5%bd%92%e5%b9%b6%e6%8e%92%e5%ba%8f%e6%95%b0%e6%8d%ae%e9%9b%86" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>让我们看一个归并连接的例子；在执行计划中由 Merge Join 节点表示：<sup id="fnref:2"><a href="#fn:2" class="footnote-ref" role="doc-noteref">2</a></sup></p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT *
</span></span><span class="line"><span class="cl">FROM tickets t
</span></span><span class="line"><span class="cl">  JOIN ticket_flights tf ON tf.ticket_no <span class="o">=</span> t.ticket_no
</span></span><span class="line"><span class="cl">ORDER BY t.ticket_no<span class="p">;</span>
</span></span><span class="line"><span class="cl">                              QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Merge Join
</span></span><span class="line"><span class="cl">   Merge Cond: <span class="o">(</span>t.ticket_no <span class="o">=</span> tf.ticket_no<span class="o">)</span>
</span></span><span class="line"><span class="cl">   −&gt; Index Scan using tickets_pkey on tickets t
</span></span><span class="line"><span class="cl">   −&gt; Index Scan using ticket_flights_pkey on ticket_flights tf
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">4</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>优化器更喜欢这种连接方式，因为它按照 ORDER BY 子句定义的方式返回排序后的结果。在选择计划时，优化器会注意到数据集的排序顺序，并且除非确实需要，否则不会执行任何排序。例如，如果归并连接生成的数据集已经具有合适的排序顺序，那么它可以直接在之后的归并连接中使用：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT *
</span></span><span class="line"><span class="cl">FROM tickets t
</span></span><span class="line"><span class="cl">  JOIN ticket_flights tf ON t.ticket_no <span class="o">=</span> tf.ticket_no
</span></span><span class="line"><span class="cl">  JOIN boarding_passes bp ON bp.ticket_no <span class="o">=</span> tf.ticket_no
</span></span><span class="line"><span class="cl">                         AND bp.flight_id <span class="o">=</span> tf.flight_id
</span></span><span class="line"><span class="cl">ORDER BY t.ticket_no<span class="p">;</span>
</span></span><span class="line"><span class="cl">                             QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Merge Join
</span></span><span class="line"><span class="cl">   Merge Cond: <span class="o">(</span>tf.ticket_no <span class="o">=</span> t.ticket_no<span class="o">)</span>
</span></span><span class="line"><span class="cl">   −&gt; Merge Join
</span></span><span class="line"><span class="cl">       Merge Cond: <span class="o">((</span>tf.ticket_no <span class="o">=</span> bp.ticket_no<span class="o">)</span> AND <span class="o">(</span>tf.flight_...
</span></span><span class="line"><span class="cl">       −&gt; Index Scan using ticket_flights_pkey on ticket_flights tf
</span></span><span class="line"><span class="cl">       −&gt; Index Scan using boarding_passes_pkey on boarding_passe...
</span></span><span class="line"><span class="cl">   −&gt; Index Scan using tickets_pkey on tickets t
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">7</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>首先要连接的表是 ticket_flights 和 boarding_passes；它们都有一个复合主键 (ticket_no, flight_id)，结果按这两列排序。然后产生的结果集与按 ticket_no 列排序的 tickets 表进行连接。</p>
<p>连接时只需对两个数据集进行一次遍历，并且不占用任何额外内存。它使用两个指针指向内层数据集和外层数据集的当前行 (最初是第一行)。</p>
<p>如果当前行的键值不匹配，其中一个指针 (引用键值较小的行) 将前进到下一行，直到找到匹配项。连接行将返回给上层节点，然后内层结果集的指针前进一位。操作持续进行，直到其中一个数据集结束。</p>
<p>此算法可以处理内层数据集的重复项，但外层数据集也可以包含它们。因此，算法需要改进：如果外指针前进后键仍然相同，则内指针回到第一个匹配行。因此，外层数据集的每一行将与内层数据集中具有相同键值的所有行匹配。<sup id="fnref:3"><a href="#fn:3" class="footnote-ref" role="doc-noteref">3</a></sup></p>
<p>对于外连接，算法稍作调整，但仍然基于相同的原则。</p>
<p>归并连接条件只能使用等值操作符，这意味着只支持等值连接 (尽管对其他条件类型的支持也在进行中)。<sup id="fnref:4"><a href="#fn:4" class="footnote-ref" role="doc-noteref">4</a></sup></p>
<p><strong>成本估算</strong>。让我们仔细看看之前的例子：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN SELECT *
</span></span><span class="line"><span class="cl">FROM tickets t
</span></span><span class="line"><span class="cl">  JOIN ticket_flights tf ON tf.ticket_no <span class="o">=</span> t.ticket_no
</span></span><span class="line"><span class="cl">ORDER BY t.ticket_no<span class="p">;</span>
</span></span><span class="line"><span class="cl">                           QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Merge Join <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>0.99..822355.54 <span class="nv">rows</span><span class="o">=</span><span class="m">8391852</span> <span class="nv">width</span><span class="o">=</span>136<span class="o">)</span>
</span></span><span class="line"><span class="cl">   Merge Cond: <span class="o">(</span>t.ticket_no <span class="o">=</span> tf.ticket_no<span class="o">)</span>
</span></span><span class="line"><span class="cl">   −&gt; Index Scan using tickets_pkey on tickets t
</span></span><span class="line"><span class="cl">       <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>0.43..139110.29 <span class="nv">rows</span><span class="o">=</span><span class="m">2949857</span> <span class="nv">width</span><span class="o">=</span>104<span class="o">)</span>
</span></span><span class="line"><span class="cl">   −&gt; Index Scan using ticket_flights_pkey on ticket_flights tf
</span></span><span class="line"><span class="cl">       <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>0.56..570972.46 <span class="nv">rows</span><span class="o">=</span><span class="m">8391852</span> <span class="nv">width</span><span class="o">=</span>32<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">6</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>连接的启动成本至少包括所有子节点的启动成本。</p>
<p>通常，可能需要在找到第一个匹配项之前扫描外层或内层数据集的一部分。可以通过比较 (基于直方图) 两个数据集中最小的连接键来估算这个比例。<sup id="fnref:5"><a href="#fn:5" class="footnote-ref" role="doc-noteref">5</a></sup> 但在这个特定的案例中，两个表中的 ticket_no 是相同的。</p>
<p>总成本包括从子节点获取数据的成本和计算成本。</p>
<p>由于连接算法在其中一个数据集结束后立即停止 (当然，除非执行外连接)，因此另一个数据集可能只被部分扫描。为了评估扫描部分的大小，我们可以比较两组数据集中的最大键值。在此示例中，两个数据集都将被完整读取，因此连接的总成本包括两个子节点的总成本之和。</p>
<p>此外，如果存在任何重复项，内层数据集的一些行可能会被多次扫描。重复扫描的预估次数等于连接结果的基数与内层数据集的基数之间的差值。<sup id="fnref:6"><a href="#fn:6" class="footnote-ref" role="doc-noteref">6</a></sup> 在这个查询中，这些基数是相同的，这意味着数据集中不包含重复项。</p>
<p>算法比较两个数据集的连接键。单次比较的成本以 <span class="marginalia" data-note="0.0025"><em>cpu_operator_cost</em></span> 进行估算，而预估的比较次数可以取为两个数据集的行数之和 (加上由于重复项导致的重复读取次数)。结果中包含的每一行的处理成本，如往常一样，以 <span class="marginalia" data-note="0.01"><em>cpu_tuple_cost</em></span> 进行估算。</p>
<p>因此，在这个例子中，连接的成本如下估计：<sup id="fnref:7"><a href="#fn:7" class="footnote-ref" role="doc-noteref">7</a></sup></p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT 0.43 + 0.56 AS startup,
</span></span><span class="line"><span class="cl">  round<span class="o">((</span>
</span></span><span class="line"><span class="cl">    139110.29 + 570972.46 +
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;cpu_tuple_cost&#39;</span><span class="o">)</span>::real * <span class="m">8391852</span> +
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="o">)</span>::real * <span class="o">(</span><span class="m">2949857</span> + 8391852<span class="o">)</span>
</span></span><span class="line"><span class="cl">  <span class="o">)</span>::numeric, 2<span class="o">)</span> AS total<span class="p">;</span>
</span></span><span class="line"><span class="cl"> startup <span class="p">|</span> 	 total
</span></span><span class="line"><span class="cl">−−−−−−−−−+−−−−−−−−−−−
</span></span><span class="line"><span class="cl">    0.99 <span class="p">|</span> 822355.54
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">1</span> row<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<h3>23.1.2 <span class="marginalia" data-note="v. 9.6"><strong>并行模式</strong></span><span class="hx-absolute -hx-mt-20" id="2312-span-classmarginalia-data-notev-96并行模式span"></span>
    <a href="#2312-span-classmarginalia-data-notev-96%e5%b9%b6%e8%a1%8c%e6%a8%a1%e5%bc%8fspan" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>虽然归并连接没有并行模式，但它仍然可以在并行计划中使用。<sup id="fnref:8"><a href="#fn:8" class="footnote-ref" role="doc-noteref">8</a></sup></p>
<p>外层数据集可以由多个工作进程并行扫描，但内层数据集总是被每个工作进程完整扫描。</p>
<p>由于并行哈希连接几乎总是成本更低，我将暂时关闭它：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SET <span class="nv">enable_hashjoin</span> <span class="o">=</span> off<span class="p">;</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>以下是使用归并连接的并行计划示例：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT count<span class="o">(</span>*<span class="o">)</span>, sum<span class="o">(</span>tf.amount<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM tickets t
</span></span><span class="line"><span class="cl">  JOIN ticket_flights tf ON tf.ticket_no <span class="o">=</span> t.ticket_no<span class="p">;</span>
</span></span><span class="line"><span class="cl">                             QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Finalize Aggregate
</span></span><span class="line"><span class="cl">   −&gt; Gather
</span></span><span class="line"><span class="cl">       Workers Planned: <span class="m">2</span>
</span></span><span class="line"><span class="cl">       −&gt; Partial Aggregate
</span></span><span class="line"><span class="cl">           −&gt; Merge Join
</span></span><span class="line"><span class="cl">               Merge Cond: <span class="o">(</span>tf.ticket_no <span class="o">=</span> t.ticket_no<span class="o">)</span>
</span></span><span class="line"><span class="cl">               −&gt; Parallel Index Scan using ticket_flights_pkey o...
</span></span><span class="line"><span class="cl">               −&gt; Index Only Scan using tickets_pkey on tickets t
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">8</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>在并行计划中不允许使用全外归并连接和右外归并连接。</p>
<h3>23.1.3 调整<span class="hx-absolute -hx-mt-20" id="2313-调整"></span>
    <a href="#2313-%e8%b0%83%e6%95%b4" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>归并连接算法可用于任何类型的连接。唯一的限制是全外连接和右外连接的连接条件必须包含归并兼容的表达式 (&quot;<em>outer-column equals inner-column</em>&quot; 或 &ldquo;<em>column equals constant</em>&quot;)。<sup id="fnref:9"><a href="#fn:9" class="footnote-ref" role="doc-noteref">9</a></sup> 内连接和左外连接仅通过不相关的条件过滤连接结果，但对于全外连接和右外连接，这种过滤是不适用的。</p>
<p>以下是使用归并算法的全外连接示例：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT *
</span></span><span class="line"><span class="cl">FROM tickets t
</span></span><span class="line"><span class="cl">  FULL JOIN ticket_flights tf ON tf.ticket_no <span class="o">=</span> t.ticket_no
</span></span><span class="line"><span class="cl">ORDER BY t.ticket_no<span class="p">;</span>
</span></span><span class="line"><span class="cl">                             QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Sort
</span></span><span class="line"><span class="cl">   Sort Key: t.ticket_no
</span></span><span class="line"><span class="cl">   −&gt; Merge Full Join
</span></span><span class="line"><span class="cl">       Merge Cond: <span class="o">(</span>t.ticket_no <span class="o">=</span> tf.ticket_no<span class="o">)</span>
</span></span><span class="line"><span class="cl">       −&gt; Index Scan using tickets_pkey on tickets t
</span></span><span class="line"><span class="cl">       −&gt; Index Scan using ticket_flights_pkey on ticket_flights tf
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">6</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>内连接和左外归并连接保留排序顺序。但是，全外连接和右外连接不能保证这一点，因为空值可以楔入外层数据集的有序值之间，这会破坏排序顺序。<sup id="fnref:10"><a href="#fn:10" class="footnote-ref" role="doc-noteref">10</a></sup> 为了恢复所需的顺序，规划器在此处引入了 Sort 节点。当然，这增加了计划的成本，使哈希连接更具吸引力，所以规划器只是因为当前禁用了哈希连接才选择了这个计划。</p>
<p>但是下一个例子不能没有哈希连接：嵌套循环根本不允许全外连接，而归并连接因为不支持的连接条件而不能使用。因此，不管 <em>enable_hashjoin</em> 参数值如何，都会使用哈希连接：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT *
</span></span><span class="line"><span class="cl">FROM tickets t
</span></span><span class="line"><span class="cl">  FULL JOIN ticket_flights tf ON tf.ticket_no <span class="o">=</span> t.ticket_no
</span></span><span class="line"><span class="cl">                             AND tf.amount &gt; <span class="m">0</span>
</span></span><span class="line"><span class="cl">ORDER BY t.ticket_no<span class="p">;</span>
</span></span><span class="line"><span class="cl">                  QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Sort
</span></span><span class="line"><span class="cl">   Sort Key: t.ticket_no
</span></span><span class="line"><span class="cl">   −&gt; Hash Full Join
</span></span><span class="line"><span class="cl">       Hash Cond: <span class="o">(</span>tf.ticket_no <span class="o">=</span> t.ticket_no<span class="o">)</span>
</span></span><span class="line"><span class="cl">       Join Filter: <span class="o">(</span>tf.amount &gt; <span class="s1">&#39;0&#39;</span>::numeric<span class="o">)</span>
</span></span><span class="line"><span class="cl">       −&gt; Seq Scan on ticket_flights tf
</span></span><span class="line"><span class="cl">       −&gt; Hash
</span></span><span class="line"><span class="cl">           −&gt; Seq Scan on tickets t
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">8</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>让我们恢复之前禁止使用哈希连接的能力：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; RESET enable_hashjoin<span class="p">;</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<h2>23.2 排序<span class="hx-absolute -hx-mt-20" id="232-排序"></span>
    <a href="#232-%e6%8e%92%e5%ba%8f" class="subheading-anchor" aria-label="Permalink for this section"></a></h2><p>如果其中一个数据集 (或可能两个数据集) 没有按连接键排序，那么在连接操作开始之前必须重新排序。这个排序操作在计划中由 Sort 节点表示：<sup id="fnref:11"><a href="#fn:11" class="footnote-ref" role="doc-noteref">11</a></sup></p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT * FROM flights f
</span></span><span class="line"><span class="cl">  JOIN airports_data dep ON f.departure_airport <span class="o">=</span> dep.airport_code
</span></span><span class="line"><span class="cl">ORDER BY dep.airport_code<span class="p">;</span>
</span></span><span class="line"><span class="cl">                       QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Merge Join
</span></span><span class="line"><span class="cl">   Merge Cond: <span class="o">(</span>f.departure_airport <span class="o">=</span> dep.airport_code<span class="o">)</span>
</span></span><span class="line"><span class="cl">   −&gt; Sort
</span></span><span class="line"><span class="cl">       Sort Key: f.departure_airport
</span></span><span class="line"><span class="cl">       −&gt; Seq Scan on flights f
</span></span><span class="line"><span class="cl">   −&gt; Sort
</span></span><span class="line"><span class="cl">       Sort Key: dep.airport_code
</span></span><span class="line"><span class="cl">       −&gt; Seq Scan on airports_data dep
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">8</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>如果在常规查询和窗口函数中指定了 ORDER BY 子句，这种排序也可以在连接上下文之外应用：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT flight_id,
</span></span><span class="line"><span class="cl">  row_number<span class="o">()</span> OVER <span class="o">(</span>PARTITION BY flight_no ORDER BY flight_id<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM flights f<span class="p">;</span>
</span></span><span class="line"><span class="cl">              QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> WindowAgg
</span></span><span class="line"><span class="cl">   −&gt; Sort
</span></span><span class="line"><span class="cl">       Sort Key: flight_no, flight_id
</span></span><span class="line"><span class="cl">       −&gt; Seq Scan on flights f
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">4</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>此处，WindowAgg 节点 <sup id="fnref:12"><a href="#fn:12" class="footnote-ref" role="doc-noteref">12</a></sup> 在数据集上计算窗口函数，该数据集已由 Sort 节点预排序。</p>
<p>规划器在其工具箱中有几种排序方法。我已经展示的示例使用了其中的两种 (Sort Method)。像往常一样，可以通过 EXPLAIN ANALYZE 命令显示这些详细信息：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>analyze,costs off,timing off,summary off<span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT * FROM flights f
</span></span><span class="line"><span class="cl">  JOIN airports_data dep ON f.departure_airport <span class="o">=</span> dep.airport_code
</span></span><span class="line"><span class="cl">ORDER BY dep.airport_code<span class="p">;</span>
</span></span><span class="line"><span class="cl">                            QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Merge Join <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">214867</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">   Merge Cond: <span class="o">(</span>f.departure_airport <span class="o">=</span> dep.airport_code<span class="o">)</span>
</span></span><span class="line"><span class="cl">   −&gt; Sort <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">214867</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">       Sort Key: f.departure_airport
</span></span><span class="line"><span class="cl">       Sort Method: external merge Disk: 17136kB
</span></span><span class="line"><span class="cl">       −&gt; Seq Scan on flights f <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">214867</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">   −&gt; Sort <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">104</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">       Sort Key: dep.airport_code
</span></span><span class="line"><span class="cl">       Sort Method: quicksort Memory: 52kB
</span></span><span class="line"><span class="cl">       −&gt; Seq Scan on airports_data dep <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">104</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">10</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<h3>23.2.1 快排<span class="hx-absolute -hx-mt-20" id="2321-快排"></span>
    <a href="#2321-%e5%bf%ab%e6%8e%92" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>如果待排序的数据集适合 <span class="marginalia" data-note="4MB"><em>work_mem</em></span> 块，则使用经典的快排方法。该算法在所有的教科书上都有介绍，此处不再过多描述。</p>
<p>至于实现，排序是由一个专用组件 <sup id="fnref:13"><a href="#fn:13" class="footnote-ref" role="doc-noteref">13</a></sup> 执行的，它根据可用的内存数量和一些其他因素选择最合适的算法。</p>
<p><strong>成本估算</strong>。让我们看看小表是如何排序的。在这种情况下，使用快排算法在内存中进行排序：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN SELECT *
</span></span><span class="line"><span class="cl">FROM airports_data
</span></span><span class="line"><span class="cl">ORDER BY airport_code<span class="p">;</span>
</span></span><span class="line"><span class="cl">                            QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Sort <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>7.52..7.78 <span class="nv">rows</span><span class="o">=</span><span class="m">104</span> <span class="nv">width</span><span class="o">=</span>145<span class="o">)</span>
</span></span><span class="line"><span class="cl">   Sort Key: airport_code
</span></span><span class="line"><span class="cl">   −&gt; Seq Scan on airports_data <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>0.00..4.04 <span class="nv">rows</span><span class="o">=</span><span class="m">104</span> <span class="nv">width</span><span class="o">=</span>...
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">3</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>已知对 n 个值进行排序的计算复杂度为 $O(n \log_2 n)$。单次比较操作估算为 <span class="marginalia" data-note="0.0025"><em>cpu_operator_cost</em></span> 值的两倍。由于在检索结果之前必须对整个数据集进行扫描和排序，因此排序的启动成本包括子节点的总成本和比较操作所产生的所有成本。</p>
<p>排序的总成本还包括返回每行的处理成本，按 <em>cpu_operator_cost</em> 进行估算 (而不是常规的 <em>cpu_tuple_cost</em> 值，因为 Sort 节点产生的开销微不足道)。<sup id="fnref:14"><a href="#fn:14" class="footnote-ref" role="doc-noteref">14</a></sup></p>
<p>对于这个例子，成本如下计算：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; WITH costs<span class="o">(</span>startup<span class="o">)</span> AS <span class="o">(</span>
</span></span><span class="line"><span class="cl">  SELECT 4.04 + round<span class="o">((</span>
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="o">)</span>::real * <span class="m">2</span> *
</span></span><span class="line"><span class="cl">      <span class="m">104</span> * log<span class="o">(</span>2, 104<span class="o">)</span>
</span></span><span class="line"><span class="cl">  <span class="o">)</span>::numeric, 2<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT startup,
</span></span><span class="line"><span class="cl">  startup + round<span class="o">((</span>
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="o">)</span>::real * <span class="m">104</span>
</span></span><span class="line"><span class="cl">	<span class="o">)</span>::numeric, 2<span class="o">)</span> AS total
</span></span><span class="line"><span class="cl">FROM costs<span class="p">;</span>
</span></span><span class="line"><span class="cl"> startup <span class="p">|</span> total
</span></span><span class="line"><span class="cl">−−−−−−−−−+−−−−−−−
</span></span><span class="line"><span class="cl">    7.52 <span class="p">|</span> 7.78
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">1</span> row<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<h3>23.2.2 Top-N 堆排序<span class="hx-absolute -hx-mt-20" id="2322-top-n-堆排序"></span>
    <a href="#2322-top-n-%e5%a0%86%e6%8e%92%e5%ba%8f" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>如果数据集只需要部分排序 (由 LIMIT 子句定义)，则可以使用堆排序方法 (在计划中显式为 top-N heapsort)。更准确地说，如果排序至少将行数减少一半，或者如果分配的内存不能容纳整个输入数据集 (而输出数据集适合)，则使用此算法。</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>analyze, timing off, summary off<span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT * FROM seats
</span></span><span class="line"><span class="cl">ORDER BY seat_no LIMIT 100<span class="p">;</span>
</span></span><span class="line"><span class="cl">                           QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Limit <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>72.57..72.82 <span class="nv">rows</span><span class="o">=</span><span class="m">100</span> <span class="nv">width</span><span class="o">=</span>15<span class="o">)</span>
</span></span><span class="line"><span class="cl">   <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">100</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">   −&gt; Sort <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>72.57..75.91 <span class="nv">rows</span><span class="o">=</span><span class="m">1339</span> <span class="nv">width</span><span class="o">=</span>15<span class="o">)</span>
</span></span><span class="line"><span class="cl">       <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">100</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">       Sort Key: seat_no
</span></span><span class="line"><span class="cl">       Sort Method: top−N heapsort Memory: 33kB
</span></span><span class="line"><span class="cl">       −&gt; Seq Scan on seats <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>0.00..21.39 <span class="nv">rows</span><span class="o">=</span><span class="m">1339</span> <span class="nv">width</span><span class="o">=</span>15<span class="o">)</span>
</span></span><span class="line"><span class="cl">           <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">1339</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">8</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>为了从 n 个值中找到 k 个最大 (或最小) 值，执行器将前 k 行添加到称为堆的数据结构中。然后将剩余的行逐一添加，并在每次迭代后从堆中删除最小 (或最大) 值。处理完所有行后，堆就包含了 k 个被寻找的值。</p>
<blockquote>
<p>这里的堆术语表示一种众所周知的数据结构，与经常被同名引用的数据库表没有任何关系。</p>
</blockquote>
<p><strong>成本估算</strong>。此算法的计算复杂度预估为 $O(n \log_2 k)$，但与快排算法相比，每个特定操作的成本更高。因此，公式使用 $n \log_2 2k$。<sup id="fnref:15"><a href="#fn:15" class="footnote-ref" role="doc-noteref">15</a></sup></p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-sql" data-lang="sql"><span class="line"><span class="cl"><span class="o">=&gt;</span><span class="w"> </span><span class="k">WITH</span><span class="w"> </span><span class="n">costs</span><span class="p">(</span><span class="n">startup</span><span class="p">)</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w"></span><span class="k">AS</span><span class="w"> </span><span class="p">(</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w">  </span><span class="k">SELECT</span><span class="w"> </span><span class="mi">21</span><span class="p">.</span><span class="mi">39</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">round</span><span class="p">((</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w">    </span><span class="n">current_setting</span><span class="p">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="p">)::</span><span class="nb">real</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="mi">2</span><span class="w"> </span><span class="o">*</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w">      </span><span class="mi">1339</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="n">log</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="w"> </span><span class="mi">2</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="mi">100</span><span class="p">)</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w">  </span><span class="p">)::</span><span class="nb">numeric</span><span class="p">,</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w"></span><span class="p">)</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w"></span><span class="k">SELECT</span><span class="w"> </span><span class="n">startup</span><span class="p">,</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w">  </span><span class="n">startup</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">round</span><span class="p">((</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w">    </span><span class="n">current_setting</span><span class="p">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="p">)::</span><span class="nb">real</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="mi">100</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w">  </span><span class="p">)::</span><span class="nb">numeric</span><span class="p">,</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="k">AS</span><span class="w"> </span><span class="n">total</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w"></span><span class="k">FROM</span><span class="w"> </span><span class="n">costs</span><span class="p">;</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w"> </span><span class="n">startup</span><span class="w"> </span><span class="o">|</span><span class="w"> </span><span class="n">total</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w"></span><span class="err">−−−−−−−−−</span><span class="o">+</span><span class="err">−−−−−−−</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w">   </span><span class="mi">72</span><span class="p">.</span><span class="mi">57</span><span class="w"> </span><span class="o">|</span><span class="w"> </span><span class="mi">72</span><span class="p">.</span><span class="mi">82</span><span class="w">
</span></span></span><span class="line"><span class="cl"><span class="w"></span><span class="p">(</span><span class="mi">1</span><span class="w"> </span><span class="k">row</span><span class="p">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<h3>23.2.3 外排<span class="hx-absolute -hx-mt-20" id="2323-外排"></span>
    <a href="#2323-%e5%a4%96%e6%8e%92" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>如果扫描显示数据集太大而无法在内存中排序，排序节点将切换到外部归并排序 (在计划中标记为 external merge)。</p>
<p>已经扫描的行在内存中通过快排算法排序并写入一个临时文件中。</p>
<img src="23-1.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>然后后续的行被读入释放的内存中，这个过程重复进行，直到所有数据被写入几个预排序的文件中。</p>
<img src="23-2.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>接下来，这些文件被合并成一个。执行此操作的算法与归并连接大致相同；主要区别在于它可以同时处理两个以上的文件。</p>
<p>合并操作不需要太多内存。实际上，每个文件有一行的空间就足够了。从每个文件中读取第一行，具有最小值 (或最大值，取决于排序顺序) 的行作为部分结果返回，释放的内存用从同一文件中获取的下一行进行填充。</p>
<p>实际上，行是以 32 页的批次读取的，而不是逐个读取，这减少了 I/O 操作的次数。单次迭代中合并的文件数取决于可用内存，但不会少于 6 个。上限也有限制 (500)，因为当文件太多时，效率会下降。<sup id="fnref:16"><a href="#fn:16" class="footnote-ref" role="doc-noteref">16</a></sup></p>
<blockquote>
<p>排序算法有着悠久的术语。外部排序最初是使用磁带执行的，而 PostgreSQL 为控制临时文件的组件保留了一个类似的名称。<sup id="fnref:17"><a href="#fn:17" class="footnote-ref" role="doc-noteref">17</a></sup> 部分排序的数据集称为 &ldquo;runs&rdquo; <sup id="fnref:18"><a href="#fn:18" class="footnote-ref" role="doc-noteref">18</a></sup>。参与合并的 &ldquo;runs&rdquo; 数称为 &ldquo;merge order&rdquo;。我没有使用这些术语，但如果你想了解 PostgreSQL 代码和注释，了解它们是值得的。</p>
</blockquote>
<p>如果排序后的临时文件不能一次性全部合并，则必须分多次处理，其部分结果被写入新的临时文件中。每次迭代都会增加要读取和写入的数据量，因此可用的 RAM 越多，外部排序完成的速度就越快。</p>
<img src="23-3.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>下一次迭代会合并新创建的临时文件。</p>
<img src="23-4.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>最终的合并通常被推迟，并在上层节点拉取数据时即时执行。</p>
<p>让我们运行 EXPLAIN ANALYZE 命令来查看外部排序使用了多少磁盘空间。BUFFERS 选项显示了临时文件(temp read 和 written) 的缓冲区使用情况。写入的缓冲区数量将 (大致) 与读取的数量相同；转换为千字节，这个值在计划中显示为 Disk：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>analyze, buffers, costs off, timing off, summary off<span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT * FROM flights
</span></span><span class="line"><span class="cl">ORDER BY scheduled_departure<span class="p">;</span>
</span></span><span class="line"><span class="cl">                       QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Sort <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">214867</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">   Sort Key: scheduled_departure
</span></span><span class="line"><span class="cl">   Sort Method: external merge Disk: 17136kB
</span></span><span class="line"><span class="cl">   Buffers: shared <span class="nv">hit</span><span class="o">=</span>2627, temp <span class="nv">read</span><span class="o">=</span><span class="m">2142</span> <span class="nv">written</span><span class="o">=</span><span class="m">2150</span>
</span></span><span class="line"><span class="cl">   −&gt; Seq Scan on flights <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">214867</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">       Buffers: shared <span class="nv">hit</span><span class="o">=</span><span class="m">2624</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">6</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>要在服务器日志中打印有关临时文件使用的更多详情，你可以启用 <em>log_temp_files</em> 参数。</p>
<p><strong>成本估算</strong>。以使用外部排序的相同计划为例：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN SELECT *
</span></span><span class="line"><span class="cl">FROM flights
</span></span><span class="line"><span class="cl">ORDER BY scheduled_departure<span class="p">;</span>
</span></span><span class="line"><span class="cl">                            QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Sort <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>31883.96..32421.12 <span class="nv">rows</span><span class="o">=</span><span class="m">214867</span> <span class="nv">width</span><span class="o">=</span>63<span class="o">)</span>
</span></span><span class="line"><span class="cl">   Sort Key: scheduled_departure
</span></span><span class="line"><span class="cl">   −&gt; Seq Scan on flights <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>0.00..4772.67 <span class="nv">rows</span><span class="o">=</span><span class="m">214867</span> <span class="nv">width</span><span class="o">=</span>63<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">3</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>此处比较成本 (其数量与内存中的快排操作数量相同) 增加了 I/O 成本。<sup id="fnref:19"><a href="#fn:19" class="footnote-ref" role="doc-noteref">19</a></sup> 所有输入数据首先必须写入磁盘上的临时文件中，然后在合并操作期间从磁盘读取 (如果所有创建的文件不能在一次迭代中合并，则可能不止一次)。</p>
<p>假定四分之三的磁盘操作 (读和写) 是顺序的，而四分之一是随机的。</p>
<p>写入磁盘的数据量取决于待排序的行数和查询中使用的列数。<sup id="fnref:20"><a href="#fn:20" class="footnote-ref" role="doc-noteref">20</a></sup> 在这个例子中，查询显示了 flights 表的所有列，因此如果不考虑其元组和页面元数据，溢出到磁盘的数据大小几乎与整个表的大小相同 (2309 页而不是 2624)。</p>
<p>此处，排序在一次迭代中完成。</p>
<p>因此，此计划中排序成本估算如下：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; WITH costs<span class="o">(</span>startup<span class="o">)</span> AS <span class="o">(</span>
</span></span><span class="line"><span class="cl">  SELECT 4772.67 + round<span class="o">((</span>
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="o">)</span>::real * <span class="m">2</span> *
</span></span><span class="line"><span class="cl">      <span class="m">214867</span> * log<span class="o">(</span>2, 214867<span class="o">)</span> +
</span></span><span class="line"><span class="cl">    <span class="o">(</span>current_setting<span class="o">(</span><span class="s1">&#39;seq_page_cost&#39;</span><span class="o">)</span>::real * 0.75 +
</span></span><span class="line"><span class="cl">     current_setting<span class="o">(</span><span class="s1">&#39;random_page_cost&#39;</span><span class="o">)</span>::real * 0.25<span class="o">)</span> *
</span></span><span class="line"><span class="cl">    <span class="m">2</span> * <span class="m">2309</span> * <span class="m">1</span> -- one iteration
</span></span><span class="line"><span class="cl">  <span class="o">)</span>::numeric, 2<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT startup,
</span></span><span class="line"><span class="cl">  startup + round<span class="o">((</span>
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="o">)</span>::real * <span class="m">214867</span>
</span></span><span class="line"><span class="cl">  <span class="o">)</span>::numeric, 2<span class="o">)</span> AS total
</span></span><span class="line"><span class="cl">FROM costs<span class="p">;</span>
</span></span><span class="line"><span class="cl"> startup  <span class="p">|</span>  total
</span></span><span class="line"><span class="cl">−−−−−−−−−−+−−−−−−−−−−
</span></span><span class="line"><span class="cl"> 31883.96 <span class="p">|</span> 32421.13
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">1</span> row<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<h3>23.2.4 <span class="marginalia" data-note="v. 13"><strong>增量排序</strong></span><span class="hx-absolute -hx-mt-20" id="2324-span-classmarginalia-data-notev-13增量排序span"></span>
    <a href="#2324-span-classmarginalia-data-notev-13%e5%a2%9e%e9%87%8f%e6%8e%92%e5%ba%8fspan" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>如果一个数据集需要按照键 $K_1$ … $K_m$ … $K_n$ 排序，并且已知该数据集已经按照前 m 个键排序，那么就不需要从头重新排序。相反，可以根据相同的前几个键 $K_1$ &hellip; $K_m$ 将数据集分成多个组（这些组内的值已经按定义的顺序排列)，然后再分别对这些组按照剩余的 $K_{m+1}$ … $K_n$ 键进行排序。这种方法称为增量排序。</p>
<p>增量排序相较其他排序算法占用的内存更少，因为它将数据集分成了几个较小的组；此外，它允许执行器在处理完第一个分组后便开始返回结果，而无需等待整个数据集排序完成。</p>
<p>在 PostgreSQL 中，实现更加微妙：<sup id="fnref:21"><a href="#fn:21" class="footnote-ref" role="doc-noteref">21</a></sup> 相对较大的组分别处理，较小的组则被合并在一起并完全排序。这减少了调用排序过程所产生的开销。<sup id="fnref:22"><a href="#fn:22" class="footnote-ref" role="doc-noteref">22</a></sup></p>
<p>执行计划中，增量排序通过 Incremental Sort 节点表示：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>analyze, costs off, timing off, summary off<span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT * FROM bookings
</span></span><span class="line"><span class="cl">ORDER BY total_amount, book_date<span class="p">;</span>
</span></span><span class="line"><span class="cl">                             QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Incremental Sort <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">2111110</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">   Sort Key: total_amount, book_date
</span></span><span class="line"><span class="cl">   Presorted Key: total_amount
</span></span><span class="line"><span class="cl">   Full−sort Groups: <span class="m">2823</span> Sort Method: quicksort Average
</span></span><span class="line"><span class="cl">   Memory: 30kB Peak Memory: 30kB
</span></span><span class="line"><span class="cl">   Pre−sorted Groups: <span class="m">2624</span> Sort Method: quicksort Average
</span></span><span class="line"><span class="cl">   Memory: 3152kB Peak Memory: 3259kB
</span></span><span class="line"><span class="cl">   −&gt; Index Scan using bookings_total_amount_idx on bookings <span class="o">(</span>ac...
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">8</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>如计划所示，数据集按 total_amount 字段预排序，因为这是在该列 (Presorted Key) 上执行索引扫描的结果。EXPLIAN ANALYZE 命令还显示了运行时统计数据。Full-sort Groups 行与被合并起来进行完全排序的小的分组相关，而 Presorted Groups 行显示了具有部分有序数据的大的分组的数据，这些数据只需要按 book_date 列进行增量排序。在这两种情况下，都使用了内存中的快排方法。组大小的差异是由于预定成本的不均匀分布造成的。</p>
<p>增量排序也可用于<span class="marginalia" data-note="v. 14">计算窗口函数</span>：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT row_number<span class="o">()</span> OVER <span class="o">(</span>ORDER BY total_amount, book_date<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM bookings<span class="p">;</span>
</span></span><span class="line"><span class="cl">                           QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> WindowAgg
</span></span><span class="line"><span class="cl">   −&gt; Incremental Sort
</span></span><span class="line"><span class="cl">       Sort Key: total_amount, book_date
</span></span><span class="line"><span class="cl">       Presorted Key: total_amount
</span></span><span class="line"><span class="cl">       −&gt; Index Scan using bookings_total_amount_idx on bookings
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">5</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p><strong>成本估算</strong>。增量排序的成本计算 <sup id="fnref:23"><a href="#fn:23" class="footnote-ref" role="doc-noteref">23</a></sup> 基于预期的组数量 <sup id="fnref:24"><a href="#fn:24" class="footnote-ref" role="doc-noteref">24</a></sup> 和对平均大小的组进行排序的预估成本 (我们已经回顾过了)。</p>
<p>启动成本反映了对第一个分组进行排序的成本估算，这使得节点可以开始返回排序后的行；总成本包括所有组的排序成本。</p>
<p>我们不打算在此处进一步探讨这些计算方式。</p>
<h3>23.2.5 <span class="marginalia" data-note="v. 10"><strong>并行模式</strong></span><span class="hx-absolute -hx-mt-20" id="2325-span-classmarginalia-data-notev-10并行模式span"></span>
    <a href="#2325-span-classmarginalia-data-notev-10%e5%b9%b6%e8%a1%8c%e6%a8%a1%e5%bc%8fspan" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>排序也可以并行进行。但是，尽管并行工作进程预先对它们的数据份额进行排序，但 Gather 节点对它们的排序顺序一无所知，只能按照先到先得的原则累积。为了保留排序顺序，执行器必须使用 Gather Merge 节点：<sup id="fnref:25"><a href="#fn:25" class="footnote-ref" role="doc-noteref">25</a></sup></p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>analyze, costs off, timing off, summary off<span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT *
</span></span><span class="line"><span class="cl">FROM flights
</span></span><span class="line"><span class="cl">ORDER BY scheduled_departure
</span></span><span class="line"><span class="cl">LIMIT 10<span class="p">;</span>
</span></span><span class="line"><span class="cl">                             QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Limit <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">10</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">   −&gt; Gather Merge <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">10</span> <span class="nv">loops</span><span class="o">=</span>1<span class="o">)</span>
</span></span><span class="line"><span class="cl">       Workers Planned: <span class="m">1</span>
</span></span><span class="line"><span class="cl">       Workers Launched: <span class="m">1</span>
</span></span><span class="line"><span class="cl">       −&gt; Sort <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">7</span> <span class="nv">loops</span><span class="o">=</span>2<span class="o">)</span>
</span></span><span class="line"><span class="cl">           Sort Key: scheduled_departure
</span></span><span class="line"><span class="cl">           Sort Method: top−N heapsort Memory: 27kB
</span></span><span class="line"><span class="cl">           Worker 0: Sort Method: top−N heapsort Memory: 27kB
</span></span><span class="line"><span class="cl">           −&gt; Parallel Seq Scan on flights <span class="o">(</span>actual <span class="nv">rows</span><span class="o">=</span><span class="m">107434</span> lo...
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">9</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>Gather Merge 节点使用二叉堆 <sup id="fnref:26"><a href="#fn:26" class="footnote-ref" role="doc-noteref">26</a></sup> 来调整由多个工作进程获取的行的顺序。它实际上合并了几个已排序的数据集，就像外部排序一样，但它用于不同的用例：Gather Merge 通常处理少量固定数量的数据源，并逐个而不是逐块地获取行。</p>
<p><strong>成本估算</strong>。Gather Merge 节点的启动成本基于其子节点的启动成本。就像 Gather 节点一样，此值增加了启动并行进程的成本 (按 <span class="marginalia" data-note="1000"><em>parallel_setup_cost</em></span> 估算) 。</p>
<p>然后，接收到的值进一步增加了构建二叉堆的成本，这需要对 n 个值进行排序，其中 n 是并行工作进程的数量 (即 $n \log_2 n$)。单个比较操作的成本预估为 <span class="marginalia" data-note="0.0025"><em>cpu_operator_cost</em></span> 的两倍，这类操作的总份额通常可以忽略不计，因为 n 相当小。</p>
<p>总成本包括通过若干个执行计划并行部分的进程获取所有数据的成本，以及将这些数据传输给领导者进程的成本。单行传输的代价预估为 <span class="marginalia" data-note="0.1"><em>parallel_tuple_cost</em></span> 加 5%，以补偿可能在获取下一个值时的等待。</p>
<p>在总成本计算中还必须考虑二叉堆更新所引起的成本：每个输入行需要 $\log_2 n$ 个比较操作和某些额外操作 (它们按 <em>cpu_operator_cost</em> 估算)。<sup id="fnref:27"><a href="#fn:27" class="footnote-ref" role="doc-noteref">27</a></sup></p>
<p>让我们看看另一个使用 Gather Merge 节点的计划。注意，这里的工作进程首先通过哈希执行部分聚合，然后 Sort 节点对接收到的结果进行排序 (成本很低，因为聚合后只剩下很少的行) ，进一步传递给领导者进程，领导者进程在 Gather Merge 节点中汇总完整的结果。至于最终的聚合，是在排序后的值列表上执行的：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN SELECT amount, count<span class="o">(</span>*<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM ticket_flights
</span></span><span class="line"><span class="cl">GROUP BY amount<span class="p">;</span>
</span></span><span class="line"><span class="cl">                            QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Finalize GroupAggregate <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>123399.62..123485.00 <span class="nv">rows</span><span class="o">=</span><span class="m">337</span> wid...
</span></span><span class="line"><span class="cl">   Group Key: amount
</span></span><span class="line"><span class="cl">   −&gt; Gather Merge <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>123399.62..123478.26 <span class="nv">rows</span><span class="o">=</span><span class="m">674</span> <span class="nv">width</span><span class="o">=</span>14<span class="o">)</span>
</span></span><span class="line"><span class="cl">       Workers Planned: <span class="m">2</span>
</span></span><span class="line"><span class="cl">       −&gt; Sort <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>122399.59..122400.44 <span class="nv">rows</span><span class="o">=</span><span class="m">337</span> <span class="nv">width</span><span class="o">=</span>14<span class="o">)</span>
</span></span><span class="line"><span class="cl">           Sort Key: amount
</span></span><span class="line"><span class="cl">           −&gt; Partial HashAggregate <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>122382.07..122385.44 r...
</span></span><span class="line"><span class="cl">               Group Key: amount
</span></span><span class="line"><span class="cl">               −&gt; Parallel Seq Scan on ticket_flights <span class="o">(</span><span class="nv">cost</span><span class="o">=</span>0.00...
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">9</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>在这里，我们有三个并行进程 (包括领导者进程)，Gather Merge 节点的成本估算如下：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; WITH costs<span class="o">(</span>startup, run<span class="o">)</span> AS <span class="o">(</span>
</span></span><span class="line"><span class="cl">  SELECT round<span class="o">((</span>
</span></span><span class="line"><span class="cl">    -- launching processes
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;parallel_setup_cost&#39;</span><span class="o">)</span>::real +
</span></span><span class="line"><span class="cl">    -- building the heap
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="o">)</span>::real * <span class="m">2</span> * <span class="m">3</span> * log<span class="o">(</span>2, 3<span class="o">)</span>
</span></span><span class="line"><span class="cl">  <span class="o">)</span>::numeric, 2<span class="o">)</span>,
</span></span><span class="line"><span class="cl">  round<span class="o">((</span>
</span></span><span class="line"><span class="cl">    -- passing rows
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;parallel_tuple_cost&#39;</span><span class="o">)</span>::real * 1.05 * <span class="m">674</span> +
</span></span><span class="line"><span class="cl">    -- updating the heap
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="o">)</span>::real * <span class="m">2</span> * <span class="m">674</span> * log<span class="o">(</span>2, 3<span class="o">)</span> +
</span></span><span class="line"><span class="cl">    current_setting<span class="o">(</span><span class="s1">&#39;cpu_operator_cost&#39;</span><span class="o">)</span>::real * <span class="m">674</span>
</span></span><span class="line"><span class="cl">  <span class="o">)</span>::numeric, 2<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">)</span>
</span></span><span class="line"><span class="cl">SELECT 122399.59 + startup AS startup,
</span></span><span class="line"><span class="cl">  122400.44 + startup + run AS total
</span></span><span class="line"><span class="cl">FROM costs<span class="p">;</span>
</span></span><span class="line"><span class="cl">  startup  <span class="p">|</span>   total
</span></span><span class="line"><span class="cl">−−−−−−−−−−−+−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> 123399.61 <span class="p">|</span> 123478.26
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">1</span> row<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<h2>23.3 非重复值和分组<span class="hx-absolute -hx-mt-20" id="233-非重复值和分组"></span>
    <a href="#233-%e9%9d%9e%e9%87%8d%e5%a4%8d%e5%80%bc%e5%92%8c%e5%88%86%e7%bb%84" class="subheading-anchor" aria-label="Permalink for this section"></a></h2><p>正如我们刚刚看到的，对值进行分组以执行聚合 (并消除重复项) 不仅可以通过哈希来执行，还可以通过排序来完成。在已排序的列表中，可以在一次遍历中挑选出重复值的组。</p>
<p>从已排序的列表中检索不同的值在计划中由一个名为 Unique 的节点表示：<sup id="fnref:28"><a href="#fn:28" class="footnote-ref" role="doc-noteref">28</a></sup></p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT DISTINCT book_ref
</span></span><span class="line"><span class="cl">FROM bookings
</span></span><span class="line"><span class="cl">ORDER BY book_ref<span class="p">;</span>
</span></span><span class="line"><span class="cl">                        QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> Result
</span></span><span class="line"><span class="cl">   −&gt; Unique
</span></span><span class="line"><span class="cl">       −&gt; Index Only Scan using bookings_pkey on bookings
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">3</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>聚合在 GroupAggregate 节点中执行：<sup id="fnref:29"><a href="#fn:29" class="footnote-ref" role="doc-noteref">29</a></sup></p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT book_ref, count<span class="o">(</span>*<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM bookings
</span></span><span class="line"><span class="cl">GROUP BY book_ref
</span></span><span class="line"><span class="cl">ORDER BY book_ref<span class="p">;</span>
</span></span><span class="line"><span class="cl">                      QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> GroupAggregate
</span></span><span class="line"><span class="cl">   Group Key: book_ref
</span></span><span class="line"><span class="cl">   −&gt; Index Only Scan using bookings_pkey on bookings
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">3</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>在并行计划中，这个节点称为 Partial GroupAggregate，而完成聚合的节点称为 Finalize GroupAggregate。</p>
<p>如果分组是通过多个列集执行的 (在 GROUPING SETS、CUBE 或 ROLLUP 子句中指定)，那么哈希和排序策略可以<span class="marginalia" data-note="v. 10">在单个节点中结合使用</span>。在不深入探讨此算法极其复杂的细节情况下，我将简单地提供一个示例，此示例在内存不足的情况下按三个不同的列执行分组：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SET <span class="nv">work_mem</span> <span class="o">=</span> <span class="s1">&#39;64kB&#39;</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT count<span class="o">(</span>*<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM flights
</span></span><span class="line"><span class="cl">GROUP BY GROUPING SETS <span class="o">(</span>aircraft_code, flight_no, departure_airport<span class="o">)</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">          QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> MixedAggregate
</span></span><span class="line"><span class="cl">   Hash Key: departure_airport
</span></span><span class="line"><span class="cl">   Group Key: aircraft_code
</span></span><span class="line"><span class="cl">   Sort Key: flight_no
</span></span><span class="line"><span class="cl">     Group Key: flight_no
</span></span><span class="line"><span class="cl">   −&gt; Sort
</span></span><span class="line"><span class="cl">       Sort Key: aircraft_code
</span></span><span class="line"><span class="cl">       −&gt; Seq Scan on flights
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">8</span> rows<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">=</span>&gt; RESET work_mem<span class="p">;</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>以下是执行此查询时发生的情况。聚合节点 (在计划中显示为 MixedAggregate) 接收按 aircraft_code 列排序的数据集。</p>
<p>首先，扫描这个数据集，并按 aircraft_code 列 (Group Key) 对值进行分组。随着扫描的进行，行按 flight_no 列重新排序 (就像由常规 Sort 节点所做的那样：如果内存足够，通过快排方法，或者使用磁盘上的外部排序)；同时，执行器将这些行放入使用 departure_airport 作为键的哈希表中 (就像通过哈希聚合所做的那样：要么在内存中，要么使用临时文件)。</p>
<p>在第二阶段，执行器扫描刚刚按 flight_no 列排序的数据集，并按相同的列分组 (Sort Key 和嵌套的 Group Key 节点)。如果行必须按另一列分组，它们将根据需要再次重新排序。</p>
<p>最后，扫描第一阶段准备的哈希表，并按 departure_airport 列分组 (Hash Key)。</p>
<h2>23.4 连接方式的比较<span class="hx-absolute -hx-mt-20" id="234-连接方式的比较"></span>
    <a href="#234-%e8%bf%9e%e6%8e%a5%e6%96%b9%e5%bc%8f%e7%9a%84%e6%af%94%e8%be%83" class="subheading-anchor" aria-label="Permalink for this section"></a></h2><p>正如我们所见，两个数据集可以通过三种不同的方式进行连接，每种方式都有其自己的优缺点。</p>
<p>嵌套循环连接没有任何前置条件，并且可以立即开始返回结果集的第一行。它是唯一一个不必完全扫描内层数据集的连接方式 (只要它可以通过索引访问)。这些属性使嵌套循环算法 (结合索引) 成为处理相对较小数据集的短 OLTP 查询的理想选择。</p>
<p>随着数据量的增长，嵌套循环的弱点变得明显。对于笛卡尔积，该算法具有平方复杂度 — 成本与被连接的数据集大小的乘积成正比。然而，笛卡尔积在实践中并不常见；对于外层数据集的每一行，执行器通常使用索引访问内层数据集的一定数量的行，这个平均数并不依赖于数据集的总大小 (例如，预订中的平均票数不会随着预订和购买的票数的增加而改变)。因此，嵌套循环算法的复杂度通常呈线性增长而不是平方增长，即使具有很高的线性系数。</p>
<p>嵌套循环算法的一个重要区别是其普适性：它支持所有连接条件，而其他方式只能处理等值连接。这允许执行带有任何类型条件的查询 (除了不能与嵌套循环一起使用的全外连接)，但你必须记住，大数据集的非等值连接很可能执行得比预期的慢。</p>
<p>哈希连接在大数据集上表现最佳。如果 RAM 足够，它只需要对两个数据集进行一次遍历，因此其复杂度是线性的。结合顺序表扫描，这种算法通常用于 OLAP 查询，这些查询基于大量数据计算结果。</p>
<p>然而，如果响应时间比吞吐量更重要，哈希连接不是最佳选择：在整个哈希表构建完成之前，它不会返回结果。</p>
<p>哈希连接算法仅适用于等值连接。另一个限制是连接键的数据类型必须支持哈希 (但几乎所有数据类型都支持)。</p>
<p>嵌套循环连接有时可以利用 <span class="marginalia" data-note="v. 14">Memoize 节点</span> (也基于哈希表) 中的内层数据集的缓存，从而击败哈希连接。虽然哈希连接总是完全扫描内层数据集，嵌套循环算法不必这样做，这可能会降低一些成本。</p>
<p>归并连接可以完美处理短的 OLTP 查询和长的 OLAP 查询。它具有线性复杂度 (要连接的集合只需扫描一次)，不需要太多内存，并且无需任何预处理即可返回结果；但是，数据集必须已经有所需的排序顺序。</p>
<p>最具成本效益的方式是通过索引扫描获取数据。如果行数较少，这是一个自然的选择；对于较大的数据集，索引扫描仍然是有效的，但前提是堆访问很少或根本不发生。</p>
<p>如果没有合适的索引可用，那么必须对数据集进行排序，但此操作是内存密集型的，其复杂度高于线性：$O(n \log_2 n)$。在这种情况下，哈希连接几乎总是比归并连接的代价更低 — 除非必须对结果进行排序。</p>
<p>归并连接的一个额外好处是内层和外层数据集的等价性。嵌套循环和哈希连接的效率都高度依赖于规划器是否可以正确分配内层和外层数据集。</p>
<p>归并连接仅限于等值联接。此外，数据类型必须具有 B 树操作符类。</p>
<p>下图表示了各种连接方式的成本与要连接的行的比例之间的大致依赖关系。</p>
<img src="23-5.png" style="width:80%; float:left" />
<div style="clear:both;"></div>
<p>如果选择性高，嵌套循环连接对两个表都使用索引访问；然后，规划器切换到外表的完全扫描，这在图表的线性部分有所反映。</p>
<p>这里的哈希连接对两个表都使用了完全扫描。图中的&quot;台阶&quot;对应于哈希表填满整个内存并且批次开始溢出到磁盘的时刻。</p>
<p>如果使用索引扫描，归并连接的成本会呈小幅线性增长。如果 <em>work_mem</em> 大小足够大，哈希连接通常更有效，但当涉及到临时文件时，归并连接会胜过它。</p>
<p>sort-merge join 的上图显示，当索引不可用并且必须对数据进行排序时，成本上升。就像哈希连接的情况一样，图上的&quot;台阶&quot;是内存不足造成的，因为它会导致使用临时文件进行排序。</p>
<p>这只是一个例子；在每种特定情况下，成本之间的比例会有所不同。</p>
<div class="footnotes" role="doc-endnotes">
<hr>
<ol>
<li id="fn:1">
<p>backend/optimizer/path/joinpath.c, generate_mergejoin_paths function&#160;<a href="#fnref:1" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:2">
<p>backend/executor/nodeMergejoin.c&#160;<a href="#fnref:2" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:3">
<p>backend/executor/nodeMergejoin.c, ExecMergeJoin function&#160;<a href="#fnref:3" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:4">
<p>For example, see commitfest.postgresql.org/33/3160&#160;<a href="#fnref:4" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:5">
<p>backend/utils/adt/selfuncs.c, mergejoinscansel function&#160;<a href="#fnref:5" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:6">
<p>backend/optimizer/path/costsize.c, final_cost_mergejoin function&#160;<a href="#fnref:6" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:7">
<p>backend/optimizer/path/costsize.c, initial_cost_mergejoin &amp; final_cost_mergejoin functions&#160;<a href="#fnref:7" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:8">
<p>backend/optimizer/path/joinpath.c, consider_parallel_mergejoin function&#160;<a href="#fnref:8" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:9">
<p>backend/optimizer/path/joinpath.c, select_mergejoin_clauses function&#160;<a href="#fnref:9" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:10">
<p>backend/optimizer/path/pathkeys.c, build_join_pathkeys function&#160;<a href="#fnref:10" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:11">
<p>backend/executor/nodeSort.c&#160;<a href="#fnref:11" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:12">
<p>backend/executor/nodeWindowAgg.c&#160;<a href="#fnref:12" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:13">
<p>backend/utils/sort/tuplesort.c&#160;<a href="#fnref:13" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:14">
<p>backend/optimizer/path/costsize.c, cost_sort function&#160;<a href="#fnref:14" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:15">
<p>backend/optimizer/path/costsize.c, cost_sort function&#160;<a href="#fnref:15" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:16">
<p>backend/utils/sort/tuplesort.c, tuplesort_merge_order function&#160;<a href="#fnref:16" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:17">
<p>backend/utils/sort/logtape.c&#160;<a href="#fnref:17" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:18">
<p><em>Donald E. Knuth</em>. The Art of Computer Programming. Volume III. Sorting and Searching&#160;<a href="#fnref:18" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:19">
<p>backend/optimizer/path/costsize.c, cost_sort function&#160;<a href="#fnref:19" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:20">
<p>backend/optimizer/path/costsize.c, relation_byte_size function&#160;<a href="#fnref:20" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:21">
<p>backend/executor/nodeIncrementalSort.c&#160;<a href="#fnref:21" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:22">
<p>backend/utils/sort/tuplesort.c&#160;<a href="#fnref:22" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:23">
<p>backend/optimizer/path/costsize.c, cost_incremental_sort function&#160;<a href="#fnref:23" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:24">
<p>backend/utils/adt/selfuncs.c, estimate_num_groups function&#160;<a href="#fnref:24" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:25">
<p>backend/executor/nodeGatherMerge.c&#160;<a href="#fnref:25" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:26">
<p>backend/lib/binaryheap.c&#160;<a href="#fnref:26" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:27">
<p>backend/optimizer/path/costsize.c, cost_gather_merge function&#160;<a href="#fnref:27" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:28">
<p>backend/executor/nodeUnique.c&#160;<a href="#fnref:28" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:29">
<p>backend/executor/nodeAgg.c, agg_retrieve_direct function&#160;<a href="#fnref:29" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
</ol>
</div>

        </div>
        <div class="hx-mt-16"></div>
        
        
      </main>
    </article>
  </div>

      <footer class="hextra-footer hx-bg-gray-100 hx-pb-[env(safe-area-inset-bottom)] dark:hx-bg-neutral-900 print:hx-bg-transparent"><div
    class="hx-max-w-screen-xl hx-mx-auto hx-flex hx-justify-center hx-py-12 hx-pl-[max(env(safe-area-inset-left),1.5rem)] hx-pr-[max(env(safe-area-inset-right),1.5rem)] hx-text-gray-600 dark:hx-text-gray-400 md:hx-justify-start"
  >
    <div class="hx-flex hx-w-full hx-flex-col hx-items-center sm:hx-items-start"><div class="hx-mt-6 hx-text-xs">本中文译文版权归熊灿灿所有。英文原文版权归 Postgres Professional 所有。本译文根据授权翻译与发布。</div>
    </div>
  </div>
</footer>
    
    <script defer src="/js/main.js" integrity=""></script>


<script defer src="/lib/flexsearch/flexsearch.bundle.min.0425860527cc9968f9f049421c7a56b39327d475e2e3a8f550416be3a9134327.js" integrity="sha256-BCWGBSfMmWj58ElCHHpWs5Mn1HXi46j1UEFr46kTQyc="></script>
    <script defer src="/en.search.js" integrity=""></script>
<link type="text/css" rel="stylesheet" href="/lib/katex/katex.min.7e5db7914b97e596a36c1abb67ccc7f174f8bb71d38c9a88c55b262ed1737f97.css" integrity="sha256-fl23kUuX5ZajbBq7Z8zH8XT4u3HTjJqIxVsmLtFzf5c=" />
  <script defer src="/lib/katex/katex.min.9f45307c5794ed247a0d095f3a62e52ef2215a67b2327203a7fd919959ae79d1.js" integrity="sha256-n0UwfFeU7SR6DQlfOmLlLvIhWmeyMnIDp/2RmVmuedE="></script>
  <script defer src="/lib/katex/auto-render.min.7b57d427ac6270677daf8d8380ded2cc73336f9149a167b8e1fe0d6ef66604ae.js" integrity="sha256-e1fUJ6xicGd9r42DgN7SzHMzb5FJoWe44f4NbvZmBK4="></script>
  <script defer src="/lib/katex/mhchem.min.f0ca03df194b8c3d6017ff455db6a0ef98857905663fa311a6cded788b15340b.js" integrity="sha256-8MoD3xlLjD1gF/9FXbag75iFeQVmP6MRps3teIsVNAs="></script>
  <script>
    
    
    document.addEventListener("DOMContentLoaded", function () {
      renderMathInElement(document.body, {
        delimiters: [
          { left: "$$", right: "$$", display: true },
          { left: "$", right: "$", display: false },
          { left: "\\(", right: "\\)", display: false },
          { left: "\\begin{equation}", right: "\\end{equation}", display: true },
          {left: "\\begin{align}", right: "\\end{align}", display: true},
          {left: "\\begin{alignat}", right: "\\end{alignat}", display: true},
          {left: "\\begin{gather}", right: "\\end{gather}", display: true},
          {left: "\\begin{CD}", right: "\\end{CD}", display: true},
          { left: "\\[", right: "\\]", display: true },
        ],
        throwOnError: false,
      });
    });
  </script>


  </body>
</html>
